package com.example.dynamicprogramming41.practice;

/**
 * @description 递归实现回溯
 * @auther lijiewei
 * @date 2022/4/9 17:32
 */
public class FlashBackPractice3 {

    /**
     * 求最短路径
     * @param money
     * @return
     * @author lijiewei
     * @date   2022/4/12 17:46
     */
    public int minCoin(int money) {
        int count;
        if (money == 1) return 1;
        if (money == 2) return 2;
        if (money == 3) return 1;
        if (money == 4) return 2;
        if (money == 5) return 1;

        count = 1 + min_dist(minCoin(money-1), minCoin(money-3), minCoin(money-5));
        System.out.println(money+"元最少硬币数量："+count);
        return count;
    }

    /**
     * 求三个数中最小值
     * @param a
     * @param b
     * @param c
     * @return
     * @author lijiewei
     * @date   2022/4/22 17:48
     */
    public int min_dist(int a, int b, int c) {
        return Math.min(Math.min(a, b), c);
    }


}
